package 链表和树.二叉树;
//Java：二叉搜索树的最近公共祖先
public class LowestCommonAncestorOfABinarySearchTree{
    public static void main(String[] args) {
        Solution solution = new LowestCommonAncestorOfABinarySearchTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
//为什么本题无需判断节点是空节点？而 236. 二叉树的最近公共祖先 这题却需要判断？
    //在BST中，我们利用了以下性质：
//两个目标节点p和q一定存在于树中（题目保证）
//利用BST的有序性质，我们可以直接判断节点在左子树还是右子树
//我们会在找到分割点时停止递归，即当p和q分别在当前节点的两侧时，或者当前节点就是p或q之一
    //在普通二叉树中：
//我们不知道节点在左子树还是右子树
//必须遍历整棵树来查找节点
//需要处理递归过程中的空节点情况
class Solution {
        //相比于上一个可以利用其的性质如果pq的值都小于当前节点那么在左子树则递归左子树返回结果
        // 大于则在右子树上
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //当前节点的值就是根节点
        int x= root.val;
        //利用其性质，直接使用值进行比较可以明确知道左递归还是右递归
        if(p.val < x && q.val <x){
            return lowestCommonAncestor(root.left , p, q);
        }
        if(p.val > x && q.val > x){
            return lowestCommonAncestor(root.right , p, q);
        }
//我们会在找到分割点时停止递归，即当p和q分别在当前节点的两侧时，
// 或者当前节点就是p或q之一
        return  root;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}